package com.yang.Tree;



import java.util.ArrayList;
import java.util.List;

public class BstTest {
    public static void main(String[] args) {
        BstTestSolution bstTestSolution = new BstTestSolution();
        int[] nums =  {3, 2, 1, 6, 0, 5};
        bstTestSolution.constructMaximumBinaryTree(nums);

    }
}

class BstTestSolution {
    private int Deep = -1;
    private int val = 0;

    private class TreeNode {
        // 1.能够存放任何类的元素
        public int val;
        // 2.拥有左右两个孩子节点
        public TreeNode left, right;

        // 二叉搜索树节点构造函数
        public TreeNode(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

    // 成员变量 1.根节点 2.记录成员数
    public TreeNode root;
    private int size;

    // 二叉搜索树根节点构造函数
    public BstTestSolution() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public Boolean isEmpty() {
        return size == 0;
    }

    public void add(int e) {
        root = add(root, e);
    }

    private TreeNode add(TreeNode node, int val) {
        if (node == null) {
            size++;
            return new TreeNode(val);
        }

        if (node.val < val) {
            node.left = add(node.left, val);
        } else if (node.val > val) {
            node.right = add(node.right, val);
        }
        // 返回根节点(保证根节点还是原来的根节点)
        return node;
    }

    public int findBottomLeftValue(TreeNode root) {
        val = root.val;
        getLeftValue(root, 0);
        return val;
    }

    public void getLeftValue(TreeNode node, int deep) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            if (deep > Deep) {
                val = node.val;
                Deep = deep;
            }

            if (node.left != null) {
                deep++;
                getLeftValue(node.left, deep);
                deep--;
            }
            if (node.right != null) {
                deep++;
                getLeftValue(node.right, deep);
                deep--;
            }
        }
    }

    public boolean hasPathSum(TreeNode root, Integer targetSum) {
        if (root == null) {
            return false;
        }
        return traverpath(root, targetSum - root.val);
    }

    public Boolean traverpath(TreeNode node, Integer count) {
        if (node.left == null && node.right == null && count == 0) {
            return true;
        }
        // 叶子节点 却没触发上面的count=0，说明不满足条件
        if (node.left == null && node.right == null) {
            return false;
        }
        if (node.left != null) {
            if (traverpath(node.left, count - node.val)) {
                return true;
            }
        }
        if (node.right != null) {
            if (traverpath(node.right, count - node.val)) {
                return true;
            }
        }
        return false;
    }

    /*
    给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
    叶子节点 是指没有子节点的节点。
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/path-sum-ii
    * */
//    public List<List<Integer>> pathsList = new ArrayList<>();
//    public List<Integer> path = new ArrayList<>();
//
//    public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
//        path.add(root.val);
//        getPathSum2(root, targetSum - root.val);
//        return pathsList;
//    }
//
//    void getPathSum2(TreeNode node, int count) {
//        if (node.left == null && node.right == null && count == 0) {
//            pathsList.add(path);
//            return;
//        }
//        if (node.left == null && node.right == null) {
//            return;
//        }
//        if (node.left != null) {
//            path.add(node.left.val);
//            getPathSum(node.left, count - node.left.val);
//            path.remove(path.size() - 1);
//        }
//        if (node.right != null) {
//            path.add(node.right.val);
//            getPathSum(node.right, count - node.right.val);
//            path.remove(path.size() - 1);
//        }
//    }

    /*    public List<List<Integer>> pathsList = new ArrayList<>();
        public List<Integer> path = new LinkedList<>();*/
//    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
//        if (root == null) {
//            return pathsList;
//        }
//        path.add(root.val);
//        getPathSum(root, targetSum - root.val);
//        return pathsList;
//    }
//
//    void getPathSum(TreeNode node, int count) {
//        if (node.left == null && node.right == null && count == 0) {
//            // 新增一个ArrayList 否则加入结果的List会被反复使用(添加其实就是添加了引用进去，所以添加几个相同引用其实是同一个对象)
//            pathsList.add(new ArrayList<>(path));
//            return;
//        }
//        if (node.left == null && node.right == null) {
//            return;
//        }
//        if (node.left != null) {
//            path.add(node.left.val);
//            getPathSum(node.left, count - node.left.val);
//            path.remove(path.size() - 1);
//        }
//        if (node.right != null) {
//            path.add(node.right.val);
//            getPathSum(node.right, count - node.right.val);
//            path.remove(path.size() - 1);
//        }
//    }

    private List<List<Integer>> pathsList;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return pathsList;
        }
        pathsList = new ArrayList();
        getPath(root, target, new ArrayList());
        return pathsList;
    }

    private void getPath(TreeNode root, int target, List<Integer> paths) {
        paths.add(root.val);
        if (root.left == null && root.right == null && target == 0) {
            pathsList.add(new ArrayList(paths));
        }
        if (root.left == null && root.right == null) {
            return;
        }
        if (root.left != null) {
            getPath(root.left, target - root.val, paths);
            paths.remove(paths.size() - 1);
        }
        if (root.right != null) {
            getPath(root.right, target - root.val, paths);
            paths.remove(paths.size() - 1);
        }
    }


    /*给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

    创建一个根节点，其值为 nums 中的最大值。
    递归地在最大值 左边 的 子数组前缀上 构建左子树。
    递归地在最大值 右边 的 子数组后缀上 构建右子树。
    返回 nums 构建的 最大二叉树  */

    // 思路和根据前后序遍历二叉树一样
    // 通过找到最大值然后进行边界的划分 (以maxValue划分左右 只剩下一个值的时候直接新建节点)
    // 找到一个最大值就创建一个节点
    // 边界条件可以是左闭右闭也可以是 左闭右开 我这次是左闭右闭
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }
    private TreeNode traversal(int[] nums, int left, int right){
        if(left - right == 0){
            return new TreeNode(nums[left]);
        }
        if(left - right < 0){
            return null;
        }
        // 从最左边开始寻找最大值
        int maxValueIndex = left;
        int maxValue = nums[left];
        for(int i = left; i <= right; i++){
            if (nums[i] > nums[maxValueIndex]){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxValue);

        root.left = traversal(nums, left, maxValueIndex - 1);
        root.right = traversal(nums, maxValueIndex + 1, right);
        return root;
    }
}

